package main.java.indi.zyj.coderecord;

public class GetMaximumGold {


    int res = 0;

    boolean[][] visited ;

    int[][] pos = new int[][]{
            {0, 1},
            {1, 0},
            {0, -1},
            {-1, 0}
    };

    public int getMaximumGold(int[][] grid) {

        int m = grid.length;
        int n = grid[0].length;
        visited = new boolean[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != 0) {
                    res = Math.max(grid[i][j], res);
                    visited[i][j] = true;
                    dfs(grid, i, j, grid[i][j]);
                    visited[i][j] = false;
                }
            }
        }

        return res;

    }

    private void dfs(int[][] grid, int i, int j, int temp) {

        for (int k = 0; k < 4; k++) {
            int nextX = i + pos[k][0];
            int nextY = j + pos[k][1];
            if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) {
                continue;
            }
            if (grid[nextX][nextY] == 0 || visited[nextX][nextY]) {
                continue;
            }
            visited[nextX][nextY] = true;
            temp += grid[nextX][nextY];
            res = Math.max(temp, res);
            dfs(grid, nextX, nextY, temp);
            visited[nextX][nextY] = false;
            temp -= grid[nextX][nextY];
        }

    }


}
